package com.hyb.algorithm.data.struct.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 全排列
 * https://leetcode.cn/problems/permutations/
 *
 * （Java）回溯 + 使用一个 boolean 数组记录 nums[i] 是否被使用，用时击败 100%
 * @author: ybhu
 * @create: 2023/12/28 18:42
 */
public class Permute {



    private List<List<Integer>> res;

    public List<List<Integer>> permute(int[] nums) {

        res=new ArrayList<List<Integer>>();
        int n=nums.length;
        boolean[] used=new boolean[n];

        backTrack(nums,0,used,new ArrayList());

        return res;

    }


    public void backTrack(int[] nums,int count,boolean[] used,List<Integer> list){

        if(count==nums.length){
            res.add(new ArrayList(list));
            return;
        }

        //和前面的 131. 分割回文串  不一样 i=0 开始， 分割回文串是 i=start
        for(int i=0;i<nums.length;i++){
            if(!used[i]){
                list.add(nums[i]);
                used[i]=true;
                //回溯
                backTrack(nums,count+1,used,list);
                used[i]=false;
                list.remove(list.size()-1);
            }
        }
    }

}
